\section{Introduction}
%Random walk computation is fundamental to distributed networks and have been used in various applications ranging from token management, load balancing, small-world routing, search, network topology construction, expansion testing, to monitoring overlays, among others. Motivated by this, Das Sarma, Nanongkai and Pandurangan~\cite{DasSarmaNP09} consider the running time of performing a random walk on the following synchronous distributed model.


%\danupon{I feel that we cite too many papers here but will wait for others decide.} \atish{I agree, specifically since we show an LB not UB - so I have shortened it a bit by reducing a few references also. The removed references are commented. So if Gopal wants to add them back he can, otherwise let's keep the current version}


The random walk plays a central role in computer science, spanning a wide range of areas in both theory and practice. The focus of this paper is on performing a random walk in distributed networks, in particular, decentralized algorithms for performing a random walk in arbitrary networks.
%
The random walk is used as an integral subroutine in a wide variety of network applications ranging from token management~\cite{IJ90,BBF04, CTW93},
%load balancing~\cite{KR04},
small-world routing~\cite{K00}, search~\cite{ZS06,AHLP01,C05,GMS05,LCCLS02}, information propagation and gathering~\cite{BAS04,KKD01}, network topology construction~\cite{GMS05,LawS03,LKRG03}, expander testing~\cite{DolevT10}, constructing random spanning
trees~\cite{Broder89, BIZ89, BFG+03},
%monitoring overlays~\cite{MG07}, group communication in ad-hoc network~\cite{DSW06}, gathering and dissemination of information over a network \cite{AKL+79},
distributed construction of expander networks \cite{LawS03}, and peer-to-peer membership management~\cite{GKM03,ZSS05}.
For more applications of random walks to distributed networks, see e.g.~\cite{DasSarmaNPT-PODC10}.
%
%Random walks  are also useful in providing uniform and efficient solutions to distributed control of dynamic networks \cite{BBSB04, ZS06}.
%Random walks are local and lightweight and require little index or state maintenance which make them especially attractive to self-organizing dynamic networks such as Internet overlay and ad hoc wireless networks.
%
Motivated by the wide applicability of the random walk, \cite{DasSarmaNP09,DasSarmaNPT-PODC10} consider the running time of performing a random walk on the synchronous distributed model. We now explain the model and problems before describing previous work and our results.


%A key purpose of random walks in  many of these network applications is to perform  node sampling.  While the sampling requirements in different applications vary, whenever a true sample is required from a random walk of certain steps, typically all applications perform the walk naively --- by simply passing a token from one node to its neighbor: thus to perform a random walk of length $\ell$ takes time linear in $\ell$.


\subsection{Distributed Computing Model}
%\paragraph{Distributed Computing Model.}
Consider a synchronous  network of processors with unbounded computational power. The network is modeled by an undirected connected $n$-node multi-graph, where nodes model the processors and  edges model the links between the processors. The processors  (henceforth, nodes) communicate  by exchanging messages via the links (henceforth, edges).  The nodes  have limited global knowledge, in particular, each of them has its own local perspective of the network (a.k.a graph), which is confined to its immediate neighborhood.


There are several measures to analyze the performance of algorithms on this model, a fundamental one being the running time, defined as the worst-case number of {\em rounds} of distributed communication. This measure naturally gives rise to a  complexity measure of problems, called the {\em time complexity}. On each round at most $O(\log n)$ bits can be sent through each edge in each direction.
%
This is a standard model of distributed computation known as the ${\cal CONGEST}$ model~\cite{peleg} and has been attracting a lot of research attention during last two decades (e.g., see \cite{peleg} and the references therein). We note that our result also holds on the ${\cal CONGEST}(B)$ model, where on each round at most $B$ bits can be sent through each edge in each direction (see the remark after Theorem~\ref{thm:rw_lower_bound}). We ignore this parameter to make the proofs and theorem statements simpler. 


\subsection{Problems}
%\paragraph{Problems.}
The basic problem is {\em computing a random walk where destination outputs source}, defined as follows.
We are given a network $G = (V,E)$ and a source node $s \in V$. The goal is to devise a distributed algorithm such that, in the end, some node $v$ outputs the ID of $s$, where $v$ is a destination node picked according to the probability that it is the destination of a random walk of length $\ell$ starting at $s$. %For short, this problem will henceforth be simply called {\em Single Random Walk}.
%
We assume the standard random walk where, in each step, an edge is taken from the current node $v$ with probability proportional to $1/d(v)$ where $d(v)$ is the degree of $v$. Our goal is to output a true  random sample from the $\ell$-walk distribution starting from $s$.

For clarity, observe that the following naive algorithm solves the above problem in $O(\ell)$ rounds. The walk of length $\ell$ is performed by sending a token for $\ell$ steps, picking a random neighbor in each step. Then, the destination node $v$ of this walk outputs the ID of $s$.
%
The main objective of distributed random walk problem is to perform such sampling with significantly less number of rounds, i.e., in time that is sublinear in $\ell$.  On the other hand, we note that it can take too much time (as much as $\Theta(|E|+D)$ time) in the ${\cal CONGEST}$  model to collect all the topological information at the source node (and then computing the walk locally).




The following variations were also previously considered.
%
\begin{enumerate}
\item \textit{Computing a random walk where source outputs destination}: The problem is almost the same as above except that, in the end, the source has to output the ID of the destination. This version is useful in nodes learning the topology of their surrounding networks and related applications such as a decentralized algorithm for estimating the mixing time \cite{DasSarmaNPT-PODC10}.

\item \textit{Computing a random walk where nodes know their positions}: Instead of outputting the ID of source or destination, we want each node to know its position(s) in the random walk. That is, if $v_1, v_2, ..., v_\ell$ (where $v_1=s$) is the result random walk starting at $s$, we want each node $v_j$ in the walk to know the number $j$ at the end of the process. This version is used to construct a random spanning tree in \cite{DasSarmaNPT-PODC10}.
\end{enumerate}


%%%%%%%%




\subsection{Previous work and our result}
%\paragraph{Previous work and our result.}

%\danupon{This paragraph is also from PODC'10.}
A key purpose of the random walk in many  network applications is to perform  node sampling.  While the sampling requirements in different applications vary, whenever a true sample is required from a random walk of certain steps, typically all applications perform the walk naively --- by simply passing a token from one node to its neighbor: thus to perform a random walk of length $\ell$ takes time linear in $\ell$.
%
%The problem of performing a random walk on distributed networks are originally solved naively in $O(\ell)$ time, as described above.
Das Sarma et al.~\cite{DasSarmaNP09} showed this is not a time-optimal strategy and the running time can be made sublinear in $\ell$, i.e., performing a random walk of length $\ell$ on an $n$-node network of diameter $D$ can be done in $\tilde O(\ell^{2/3}D^{1/3})$ time where $\tilde O$ hides $\polylog n$. Subsequently, Das Sarma et al.~\cite{DasSarmaNPT-PODC10} improved this bound to $\tilde O(\sqrt{\ell D}+D)$ which holds for all three versions of the problem.


There are two key motivations for obtaining sublinear time bounds. The first is that in many algorithmic applications, walks of length significantly greater than the network diameter are needed.  For example, this is necessary in two applications presented in \cite{DasSarmaNPT-PODC10}, namely distributed computation of a random
spanning tree (RST) and computation of mixing time. More generally, many real-world communication networks  (e.g., ad hoc networks and peer-to-peer networks) have relatively small diameter, and random walks of length at least the diameter are usually performed for many sampling applications, i.e., $\ell >> D$.

The second motivation is understanding the time complexity of distributed random walks. Random walk is essentially a global problem  which requires the algorithm to ``traverse" the entire network. Classical ``global" problems include the minimum spanning tree, shortest path etc. Network diameter is an inherent lower bound for such problems. Problems of this type raise the basic question whether $n$ (or $\ell$ as the case here) time is essential or is the network diameter $D$, the inherent parameter. As pointed out in the seminal work of \cite{peleg-mst}, in the latter case, it would be desirable to design algorithms that have a better complexity for graphs with low diameter. While both upper and lower bounds of time complexity of many ``global'' problems are known (see, e.g., \cite{DasSarmaHKKNPPW10}), the status of the random walk problem is still wide open.
%\danupon{More stuff from PODC'10 is commented below.}


%There are two key motivations for obtaining sublinear time bounds.
%The first is that in many algorithmic applications, walks of length
%significantly greater than the network diameter are needed. For
%example, this is necessary in both the  applications   presented
%later in the paper, namely distributed computation of a random
%spanning tree (RST) and  computation of mixing time. In the RST
%algorithm, we need to perform a random walk of expected length
%$O(mD)$ (where $m$ is the number of edges in the network). In
%decentralized computation of mixing time, we need to perform walks
%of length at least the mixing time which can be significantly larger
%than the diameter (e.g., in a random geometric graph model
%\cite{MP}, a popular model for ad hoc networks, the mixing time can
%be larger than the diameter by a factor of $\Omega(\sqrt{n})$.) More
%generally, many real-world communication networks  (e.g., ad hoc
%networks and peer-to-peer networks) have relatively small diameter,
%and random walks of length at least the diameter are usually
%performed for many sampling applications, i.e., $\ell >> D$. It
%should be noted that  if the network is rapidly mixing/expanding
%which is sometimes the case in practice, then sampling from walks of
%length $\ell >> D$ is close to sampling from the steady state
%(degree) distribution; this can be done in $O(D)$ rounds (note
%however, that this gives only an approximately close sample, not the
%exact sample for that length). However, such an approach fails when
%$\ell$ is smaller than the mixing time.

A preliminary attempt to show a random walk lower bound is presented in \cite{DasSarmaNPT-PODC10}. They consider a restricted class of algorithms, where each message sent between nodes must be in the form of an interval of numbers. Moreover, a node is allowed to send a number or an interval containing it only after it receives such number. For this very restricted class of algorithms, a lower bound of $\Omega(\sqrt{\ell}+D)$ is shown~\cite{DasSarmaNPT-PODC10} for the version where every node must know their positions in the end of the computation.
%
While this lower bound shows a potential limitation of random walk algorithms,
it has many weaknesses. First, it does not employ an information theoretic argument and thus does not hold for all types of algorithm. In stead, it assumes that the algorithms must send messages as intervals and thus holds only for a small class of algorithms, which does not even cover all deterministic algorithms.
%
Second, the lower bound holds only for the version where nodes know their position(s), thereby leaving lower bounds for the other two random walk versions completely open. 
%
More importantly, there is still a gap of $\sqrt{D}$ between lower and upper bounds, leaving a question whether there is a faster algorithm.

%\danupon{Sami and Twigg~\cite{ST08} consider lower bounds on the communication complexity of computing stationary distribution of random walks in a network. Although, their problem is related to our problem, the lower bounds obtained do not imply anything in our setting.}

Motivated by these applications, past results, and open problems, we consider the problem of finding lower bounds for random walk computation. In this work, we show an {\em unconditional} lower bound of $\Omega(\sqrt{\ell D}+D)$ for all three versions of the random walk computation problem. This means that the algorithm in \cite{DasSarmaNPT-PODC10} is optimal for all three variations. In particular, we show the following theorem.

%\begin{theorem}\label{thm:rw_lower_bound}
%%For any $B$, $D$ and $\ell\geq D$, there exists a family of networks of diameter $\Theta(D)$ such that performing a random walk of length $\ell$ on these networks requires $\Omega(\sqrt{\ell D})$ rounds in the $B$-model.
%%
%For any $n$, $B$, $D$ and $\ell$ such that $\ell\geq D$ and $n\geq B \ell^4D^2$, there exists a family of $\Theta(n)$-node networks of diameter $\Theta(D)$ such that performing a random walk of length $\Theta(\ell)$ on these networks requires $\Omega(\sqrt{\ell D}+D)$ rounds in the $B$-model.
%\end{theorem}

% THIS IS BEFORE WE IGNORE B
%\begin{theorem}\label{thm:rw_lower_bound}
%For any $n$, $B$, $D$ and $\ell$ such that $D\leq \ell\leq (n/(B D^2))^{1/4}$, there exists a family of $n$-node networks of diameter $D$ such that performing a random walk of length $\Theta(\ell)$ on these networks requires $\Omega(\sqrt{\ell D}+D)$ rounds in the $B$-model.
%\end{theorem}

\begin{theorem}\label{thm:rw_lower_bound}
For any $n$, $D$ and $\ell$ such that $D\leq \ell\leq (n/(D^3\log n))^{1/4}$, there exists a family of $n$-node networks of diameter $D$ such that performing a random walk (any of the three versions) of length $\Theta(\ell)$ on these networks requires $\Omega(\sqrt{\ell D}+D)$ rounds.
\end{theorem}


%\danupon{Remark: Can also convert to a simple graph (but $n$ will be much larger).}
%\danupon{Remark: The lower bound also holds for an approximation algorithm (output destination with approximated random walk distribution).}
%
%\atish{if we say $B$-model, shouldn't we put the $B$ into the lower bound also?}\danupon{$B$ affects $n$ but not the lower bound.}
%\atish{although this is more general, it seems a little hard to parse. Should we instead say "There exists a family of $n$-node graphs with diameter $D$ such that performing a random walk of length $\ell$ from a specified source for some $\ell \geq D$ and $\ell \le (l/D^2)^{1/4}$, requires .... "? Not sure maybe the current version is better.}
%\danupon{Simplying the above statement should be good. But I think it's dangerous to ignore saying ``for any $n$, $B$, $\ell$ and $D$'' since then people might think that this is only the existential bound (i.e., it's true for some values).}

%In particular, for $B=\log n$ as usually assumed, we have that if $\ell\geq D$ and $n\geq \ell^4D^2\log n$ then performing a random walk of length $\Theta(\ell)$ requires $\Omega(\sqrt{\ell D})$ rounds.
%
%We note that the parameter $B$ affects the graph size but not the lower bound.
%
We note that our lower bound of $\Omega(\sqrt{\ell D}+D)$ also holds for the general ${\cal CONGEST}(B)$ model, where each edge has bandwidth $B$ instead of $O(\log n)$, as long as $\ell\leq (n/(D^3 B))^{1/4}$.
%
Moreover, one can also show a lower bound on simple graphs by subdividing edges in the network used in the proof and double the value of $\ell$. 

\subsection{Techniques and proof overview}
%\paragraph{Techniques overview.}

Our main approach relies on enhancing the connection between communication complexity and distributed algorithm lower bounds first studied in \cite{DasSarmaHKKNPPW10}. It has been shown in \cite{DasSarmaHKKNPPW10} that a fast distributed algorithm for computing a function can be converted into a two-party communication protocol with small message complexity to compute the same function. In other words, the communication complexity lower bounds implies the time complexity lower bounds of distributed algorithms. This result is then used to prove lower bounds on many {\em verification problems}. (In the verification problems, we are given $H$, a subgraph of the network  $G$, where each vertex of $G$ knows which edges incident on it are in $H$. We would like to verify whether $H$ has some properties, e.g., if it is a tree or if it is connected.) The lower bounds of verification problems are then used to prove lower bounds of approximation algorithms for many graph problems. Their work, however, does not make progress on achieving {\em any} unconditional lower bound on the random walk problem.
%\atish{I've made minor changes to this subsection. It looks good overall. My main concern with this section is that it still seems like we are building on the stoc submission by adding another problem to the long list of problems we've shown to have LBs. Instead, it would be nice to position this paper more as a follow up to our PODC papers than the stoc submission. In terms of techniques, though, I agree that it is more of a follow-up to stoc submission. So not sure. What do you think is the best way to place this section?}\danupon{I think someone will ask what the difference between this paper and the stoc submission and this is the best answer I have. We can add some more paragraphs to emphasize the fact that this is a follow-up (or even an ending) of the random walk series. But I think this is not a good place - we should have done that in previous sections, if we haven't already done so.}

Further, while this approach has been successfully used to show lower bounds for several problems in terms of network size (i.e., $n$), it is not clear how to apply them to random walk computation. All the lower bounds previously shown are for {\em optimization} problems for well-defined metrics - for e.g. computing a minimum spanning tree. Random walk computation, on the other hand, is not deterministic; the input requires parameters such as the length of the walk $\ell$ and even if the source node and $\ell$ are fixed, the {\em solution} (i.e. the walk) is not uniquely determined. While even other problems, such as MST, can have multiple solutions, for optimization problems, {\em verification} is well-defined. It is not clear what it even means to verify whether a random walk is {\em correct}. For this reason, proving a lower bound of random walk computation through verification problems seems impossible.

Additionally, in terms of the theoretical bound we obtain, a key difficulty in our result is to introduce the graph parameter diameter (i.e., $D$) into the lower bound multiplied by $\ell$. A crucial shortcoming in extending previous work in this regard is that the relationship between communication complexity and distributed computing shown in \cite{DasSarmaHKKNPPW10} does not depend on the network diameter $D$ at all. In fact, such a relationship might not exist since the result in \cite{DasSarmaHKKNPPW10} is tight for some functions.

To overcome these obstacles, we consider a variation of communication complexity called {\em  $r$-round two-party communication complexity}, which has been successfully used in, e.g., circuit complexity and data stream computation (see, e.g., \cite{FeigenbaumKMSZ08,NisanW93}). We obtain a new connection showing that a fast distributed algorithm for computing a function can be converted to a two-party communication protocol with a small message complexity {\em and number of rounds} to compute the same function. Moreover, the larger the network diameter is, the smaller the number of rounds will be.
%
To obtain this result one need to deal with a more involved proof; for example, the new proof does not seem to work for the networks previously considered \cite{DasSarmaHKKNPPW10,Elkin06,LotkerPP06,PelegR00} and thus we need to introduce a novel network called $\graph$. This result and related definitions are stated and proved in Section~\ref{sec:communication_complexity}.


A particular communication complexity result that we will use is that of Nisan and Wigderson~\cite{NisanW93} for the {\em $r$-round pointer chasing problem}. Using the connection established in Section~\ref{sec:communication_complexity}, we derive a lower bound of any distributed algorithms for solving the pointer chasing problem on a distributed network. This result is in Section~\ref{sec:pointer_chasing}.


Finally, we prove Theorem~\ref{thm:rw_lower_bound} from the lower bound result in Section~\ref{sec:pointer_chasing}. The main idea, which was also used in \cite{DasSarmaNPT-PODC10}, is to construct a network that has the same structure as $\graph$ (thus has the same diameter and number of nodes) but different edge capacities (depending on the input) so that a random walk follows a desired path (which is unknown) with high probability.
%We note that we prove the result directly instead of proving via graph verification problems as in \cite{DasSarmaNPT-PODC10,DasSarmaHKKNPPW10}.
%One can also think of this as proving implicitly via a ``search'' problem (in particular, searching an end node of a path).
This proof is in Section~\ref{sec:main_theorem}.

